#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_V 10 // 最大顶点数

// 图结构（邻接矩阵）
typedef struct
{
    int matrix[MAX_V][MAX_V]; // 邻接矩阵
    char *vertex[MAX_V];      // 顶点名称数组
    int vCount;               // 当前顶点数
} Graph;

// 1. 创建图
Graph *createGraph()
{
    Graph *g = (Graph *)malloc(sizeof(Graph));
    g->vCount = 0;

    // 初始化邻接矩阵
    for (int i = 0; i < MAX_V; i++)
    {
        for (int j = 0; j < MAX_V; j++)
        {
            g->matrix[i][j] = 0;
        }
        g->vertex[i] = NULL;
    }
    return g;
}

// 2. 添加顶点
void addVertex(Graph *g, const char *name)
{
    if (g->vCount >= MAX_V)
    {
        printf("Error: Graph is full\n");
        return;
    }
    g->vertex[g->vCount] = strdup(name);
    g->vCount++;
}

// 3. 添加边（无向图）
void addEdge(Graph *g, int v1, int v2)
{
    if (v1 < 0 || v1 >= g->vCount || v2 < 0 || v2 >= g->vCount)
    {
        printf("Error: Invalid vertex index\n");
        return;
    }
    g->matrix[v1][v2] = 1;
    g->matrix[v2][v1] = 1; // 无向图对称
}

// 4. 打印图
void printGraph(Graph *g)
{
    printf("Adjacency Matrix:\n");

    // 打印表头
    printf("     ");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("%-5s", g->vertex[i]);
    }
    printf("\n");

    // 打印矩阵
    for (int i = 0; i < g->vCount; i++)
    {
        printf("%-5s", g->vertex[i]);
        for (int j = 0; j < g->vCount; j++)
        {
            printf("%-5d", g->matrix[i][j]);
        }
        printf("\n");
    }
}

// 5. 销毁图
void destroyGraph(Graph *g)
{
    if (!g)
        return;

    // 释放顶点名称
    for (int i = 0; i < g->vCount; i++)
    {
        free(g->vertex[i]);
    }

    // 释放图结构
    free(g);
}

int main()
{
    // 创建图
    Graph *g = createGraph();

    // 添加顶点
    addVertex(g, "A");
    addVertex(g, "B");
    addVertex(g, "C");
    addVertex(g, "D");

    // 添加边
    addEdge(g, 0, 1); // A-B
    addEdge(g, 0, 2); // A-C
    addEdge(g, 1, 3); // B-D
    addEdge(g, 2, 3); // C-D

    // 打印图
    printGraph(g);

    // 销毁图
    destroyGraph(g);

    return 0;
}